package _back_tracking

import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/beautiful-arrangement/description
 * 526. 优美的排列
 *
 *
 * ```
 * 假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
 * perm[i] 能够被 i 整除
 * i 能够被 perm[i] 整除
 * 给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
 *
 * 示例 1：
 * 输入：n = 2
 * 输出：2
 * 解释：
 * 第 1 个优美的排列是 [1,2]：
 *     - perm[1] = 1 能被 i = 1 整除
 *     - perm[2] = 2 能被 i = 2 整除
 * 第 2 个优美的排列是 [2,1]:
 *     - perm[1] = 2 能被 i = 1 整除
 *     - i = 2 能被 perm[2] = 1 整除
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：1
 *
 *
 * 提示：
 * 1 <= n <= 15
 * ```
 */
class leetcode_526 {
    @Test
    fun test_1() {
        val result = countArrangement(2)
        val expected = 2
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_2() {
        val result = countArrangement(1)
        val expected = 1
        Assert.assertEquals(expected, result)
    }

    private fun countArrangement(n: Int): Int {
        /**
         * 回溯
         * https://blog.csdn.net/lirendada/article/details/145429699
         */
        // 用作打印path
        val path: ArrayList<Int> = ArrayList()
        f(n, 1, BooleanArray(n + 1), path)
        return count
    }

    var count: Int = 0


    private fun f(n: Int, tail: Int, used: BooleanArray, path: ArrayList<Int>) {
        // 1  确认函数参数以及返回值
        // tail表示当前构造到数组的尾部下标，从1开始

        // 2 确定终止条件
        if (tail > n) {
            // 说明前面一直是符合条件的
            // 收集结果
            count++
            println(path)
            return
        }

        // 3 确认循环
        for (i in 1..n) {
            // 处理节点
            // 不（满足条件之一）
            if (tail % i != 0 && i % tail != 0) {
                continue
            }

            // 2 种去重方式，选择一种即可。
            // 去重方式1 ：used[i] == true
            if (used[i] == true) {
                continue
            }
            // 去重方式2:path.contains(i)
            if(path.contains(i)){
                continue
            }

            used[i] = true
            path.add(i)
            println("i=$i")

            // 递归
            f(n, tail + 1, used, path)

            // 回溯
            used[i] = false
            path.removeAt(path.size - 1)

            // 4 剪枝
            // 5 去重： 树枝
        }
    }
}